/*
 * @lc app=leetcode.cn id=1631 lang=swift
 *
 * [1631] 最小体力消耗路径
 */

// @lc code=start
class Solution {
    func minimumEffortPath(_ heights: [[Int]]) -> Int {
        let dirs: [(Int, Int)] = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        let m = heights.count
        let n = heights[0].count

        var distTo: [[Int]] = Array(repeating: Array(repeating: Int.max, count: n), count: m)
        distTo[0][0] = 0

        var pq: [(Int, Int, Int)] = []
        pq.append((0, 0, 0))

        while !pq.isEmpty {
            let curNode = pq.removeFirst()
            let curNodeX = curNode.0
            let curNodeY = curNode.1
            let curNodeDist = curNode.2

            // 到达终点
            if curNodeX >= m - 1 && curNodeY >= n - 1 {
                return curNodeDist
            }

            if curNodeDist > distTo[curNodeX][curNodeY] {
                continue
            }

            for dir in dirs {
                let nextNodeX = curNodeX + dir.0
                let nextNodeY = curNodeY + dir.1
                if nextNodeX < 0 || nextNodeY < 0 || nextNodeX >= m || nextNodeY >= n {
                    continue
                }
                let nextNodeDist = max(distTo[curNodeX][curNodeY], abs(heights[nextNodeX][nextNodeY] - heights[curNodeX][curNodeY]))
                if nextNodeDist < distTo[nextNodeX][nextNodeY] {
                    distTo[nextNodeX][nextNodeY] = nextNodeDist
                    pq.append((nextNodeX, nextNodeY, nextNodeDist))
                    pq.sort(by: { a, b in a.2 < b.2 })
                }
            }
        }

        return 0
    }
}
// @lc code=end

